//输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。 
//
// 
//
// 示例 1： 
//
// 输入：arr = [3,2,1], k = 2
//输出：[1,2] 或者 [2,1]
// 
//
// 示例 2： 
//
// 输入：arr = [0,1,2,1], k = 1
//输出：[0] 
//
// 
//
// 限制： 
//
// 
// 0 <= k <= arr.length <= 10000 
// 0 <= arr[i] <= 10000 
// 
//
// Related Topics 数组 分治 快速选择 排序 堆（优先队列） 👍 559 👎 0


package leetcode.editor.cn;

// [剑指 Offer 40]最小的k个数

import java.util.Arrays;

public class ZuiXiaoDeKgeShuLcof_JianZhiOffer40 {
    public static void main(String[] args) {
        Solution solution = new ZuiXiaoDeKgeShuLcof_JianZhiOffer40().new Solution();
        int[] leastNumbers = solution.getLeastNumbers(new int[]{0, 1, 1, 2, 4, 4, 1, 3, 3, 2}, 6);
        System.out.println(Arrays.toString(leastNumbers));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int[] getLeastNumbers(int[] arr, int k) {
            generateHeap(arr, k);
            for (int i = k; i < arr.length; i++) {
                if (arr[i] < arr[0]) {
                    swap(arr, 0, i);
                    heapify(arr, k);
                }
            }
            return Arrays.copyOf(arr, k);
        }

        public void heapify(int[] arr, int k) {
            int cur = 0;
            int idx;
            while (2 * cur + 1 < k) {
                if (2 * cur + 2 < k) {
                    idx = arr[2 * cur + 1] > arr[2 * cur + 2] ? 2 * cur + 1 : 2 * cur + 2;
                } else {
                    idx = 2 * cur + 1;
                }
                if (arr[cur] < arr[idx]) {
                    swap(arr, cur, idx);
                    cur = idx;
                } else {
                    break;
                }
            }
        }

        public void generateHeap(int[] arr, int k) {
            int n = arr.length;
            if (n < 2 || k == 1) {
                return;
            }
            int cur;
            int fater;
            for (int i = 1; i < k; i++) {
                cur = i;
                fater = (cur - 1) >> 1;
                while (fater >= 0 && arr[cur] > arr[fater]) {
                    swap(arr, cur, fater);
                    cur = fater;
                    fater = (cur - 1) >> 1;
                }
            }
        }

        public void swap(int[] arr, int i, int j) {
            int tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}